package main.sort.java;

public class SortMerge extends Swap implements Sort {
    @Override
    public void execute(int[] ar) {
        sortMerge(ar, 0, ar.length - 1);
    }

    private void sortMerge(int[] ar, int left, int right) {
        if (left >= right) {return;}
        int mid = (left + right) >> 1;
        sortMerge(ar, left, mid);
        sortMerge(ar, mid + 1, right);
        merge(ar, left, mid, right);
    }

    private void merge(int[] ar, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (ar[i] <= ar[j]) {temp[k++] = ar[i++];} else {temp[k++] = ar[j++];}
        }
        while (i <= mid) {temp[k++] = ar[i++];}
        while (j <= right) {temp[k++] = ar[j++];}

        while (k > 0) {ar[--j] = temp[--k];}
    }
}